#ifndef _NOLOCK_H_
#define _NOLOCK_H_

// a non-locking hash table for use with threaded functions
#include "util.h"
#include "jobqueue.h"

// the key is always a uint64
//   0 is not a valid key. 
template<class Value> 
struct NLHash {
  struct Entry {
    uint64 key_;
    Value value_;
  };
  NLHash(uint64 lg_size, bool zero_out = true) {
    size_ = 1 << lg_size;
    CHECK(size_);
    mod_mask_ = size_ - 1;
    data_ = new Entry[size_];
    if (zero_out)
      for (uint64 i=0; i<size_; i++) {
	data_[i].key_ = 0;
	data_[i].value_ = 0;
      }
    max_look_ = 0;
  }
  Value * Lookup(uint64 key, bool insert = false) {
    uint64 pos = key & mod_mask_;
    uint64 step = 0;
    while(1) {
      uint64 k = data_[pos].key_;
      if (k == key) {
	// matched the key
	return &(data_[pos].value_);
      }
      if (k == 0) {
	if (!insert) return NULL;
	bool success = __sync_bool_compare_and_swap(&data_[pos].key_, 0, key);
	if (success) return &(data_[pos].value_);
	// CHECK(data_[pos].key_);
	if (data_[pos].key_ == key) return &(data_[pos].value_);
      }
      pos = (pos + (++step)) & mod_mask_;
      if (step > max_look_) max_look_ = step;
      continue;      
    }    
  }
  Value * InsertOrReturn(uint64 key) { return Lookup(key, true); }

  /*
  // TODO: not sure this is really working, not using reorgshard ...
  // returns true if something moved.  Need to repeat until nothing moves
  bool ReorgShard(uint64 shard = 0, uint64 num_shards = 1) {
    bool moved = false;
    uint64 begin = shard * size_ / num_shards;
    uint64 end = (shard + 1) * size_ / num_shards;
    for (uint64 pos = begin; pos < end; pos++) {
      Value * new_val = InsertOrReturn(data_[pos].key_);
      if (new_val != &data_[pos].value_) {
	*new_val = data_[pos].value_;
	data_[pos] = Entry();
	moved = true;
      }
    }
    return moved;
  }
  void SingleThreadedReorg() { while (ReorgShard()); }
  struct ReorgTask {
    void Run() { 
      if (nlhash_->ReorgShard(shard_, num_shards_)) {
	*moved_ = true;
      } 
    }
    NLHash * nlhash_;
    uint64 shard_;
    uint64 num_shards_;
    bool * moved_;
  };
  void JobQueueReorg(int num_shards) {
    while (1) {
      JobQueue::Job j;
      bool moved;
      for (uint64 shard = 0; shard<num_shards; shard++) {
	ReorgTask * t = new ReorgTask;
	t->nlhash_ = this;
	t->shard_ = shard;
	t->num_shards_ = num_shards;
	t->moved_ = &moved;
      }
      if (!moved) return;
    }    
  }

  */
  
  void JQZero(JobQueue * jq) {
    JobQueueZero(jq, data_, size_ * sizeof(Entry));
    max_look_ = 0;
  }

  // for linear iteration
  uint64 Size() const { return size_; }
  uint64 & KeyRef(uint64 n) { return data_[n].key_;}
  Value & ValueRef(uint64 n) { return data_[n].value_;}
  
  Entry *data_;
  uint64 size_;
  uint64 mod_mask_;
  uint64 max_look_;
};

#endif
